package protect.week01;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/1 17:23
 * @package protect.week01
 * @description x 的平方根
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 * <p>
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 * <p>
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 * <p>
 *  
 * 示例 1：
 * <p>
 * 输入：x = 4
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sqrtx
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Ch04_MySqrt {
    public static int mySqrt(int x) {

        if (x == 0) {
            return 0;
        }

        for (int i = 0; i < x; i++) {
            if (i * i == x || x < (long) (i + 1) * (i + 1)) {
                return i;
            }
        }

        return 1;
    }

    public static int mySqrt2(int x) {

        /*
        分析：
            10
            1 * 1 = 1 < 10
            2 * 2 = 4 < 10
            3 * 3 = 9 < 10
            4 * 4 = 16 > 10
            10 的平方根是 在 3 - 4 之间

            ==>> 从 1 开始循环，求出数字的平方与目标数字进行比较，
                    如果小于，则继续判断
                    如果等于，则次数为平方根数字
                    如果大于，则前面一个数字是平方根数字
         */

        for (int i = 1; i <= x; i++) {
            long squarei = (long) i * i;
            if (squarei == x) {
                return i;
            } else if (squarei > x){
                return i - 1;
            }
        }
        return 0;
    }


    public static void main(String[] args) {
        System.out.println(mySqrt2(4));
    }
}
